package search.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : GenerateParentheses
 * @Description : 22. 括号生成
 * https://leetcode.cn/problems/generate-parentheses/
 * @Author : chentianyu
 * @Date 2023/3/6 00:01
 */


public class GenerateParentheses {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        generateParenthesisHelper(ans, "", n, n);
        return ans;
    }

    private void generateParenthesisHelper(List<String> ans, String str, int l, int r) {
        if (l == 0 && r == 0) {
            ans.add(str.toString());
            return;
        }

        // 核心算法：若剩余的左括号数量大于剩余的右括号数量，则组合必定无效！
        // ① 当左括号数量等于右括号数量时，必须先使用左括号；
        // ② 当左括号数量小于右括号数量时，即可使用左括号，也可使用右括号。
        if (l == r) {
            generateParenthesisHelper(ans, str + "(", l - 1, r);
        } else if (l < r){
            if (l > 0) {
                generateParenthesisHelper(ans, str + "(", l - 1, r);
            }
            generateParenthesisHelper(ans, str + ")", l, r - 1);
        }
    }

}
